Continuous tone still images can be stored electronically in digital form as matrices of quantized analog values. Each matrix is a two-dimensional grid of individual picture elements or “pixels.” Each pixel has an integer value representing a color or grayscale tonal value on an integer-based gradient scale. For example, a single 16-bit pixel value represents one color picked from a palette consisting of 65,536 individual colors. The pixel values for each image are stored into a file representing the image rendered at a set dimension, such as 640×480 pixels.
In raw uncompressed form, the size of a digital image file increases dramatically with the size of the color palette and image dimensions. A richer color palette requires more integer values and a larger dimensioned image requires an increased number of pixels. Fortunately, digital image storage benefits from compression techniques which take advantage of repetitive or otherwise structured data and which can compress the size of a digital image file into a more manageable size. The Joint Photographic Expert Group (JPEG) file format is presently the most commonly used format for compressing photo-realistic digital image file data, and is described in G. K. Wallace, “The JPEG Still Picture Compression Standard,” Comm. of the ACM (April 1991), and W. B. Pennebaker et al., “JPEG Still Image Data Compression Standard,” Van Nostrad Rhinehold (1993), the disclosures of which are incorporated by reference.
Increasingly, digital images are being exchanged between interconnected networks of computer systems, including over the Internet, as well as with lightweight clients, such as personal data assistants (PDAs) and cellular telephones. Conventionally, the ability to exchange data, including digital images, over a network, is limited by the network bandwidth available to each device. The bandwidth is affected by the capability of the network itself as well as by the means by which each client is interconnected. A slow modem connection, for instance, is a form of low bandwidth connection that can restrict the ability of an individual client to exchange data. Lower bandwidth means longer download times for larger file sizes. Low bandwidth is particularly problematic when receiving digital images as content embedded, for instance, in Web pages.
One solution to the low bandwidth problem is to recompress images that are already stored in a compressed format, such as the JPEG file format, to further conserve on space and bandwidth requirements. The JPEG file format, however, is an image compression file format that is mostly used in a “lossy” version, that is, a version that loses information upon compression. As well, successive recompressions will result in additional data loss and in the formation of visual artifacts which deteriorate the perceptual quality of an image.
Moreover, the compression and recompression of images using the JPEG file format can result in unpredictable and quite surprising changes. A widely used quality scale was implemented by the Independent JPEG Group (IJG). The quality scale offers compression at predefined quality levels on a range of Q1 (very low quality) to Q100 (excellent quality). In general, higher quality levels correspond to larger file sizes. However, this quality scale is not perceptually monotone. A larger file size does not necessarily correspond to better perceptual quality. When recompressing an already once-compressed JPEG image, lower quality settings can actually result in better perceptual quality, such as described in S. Chan, “Recompression of Still Images,” Tech. Rep. 2-92, Univ. of Kent, Canterbury, UK (March 1992), the disclosure of which is incorporated by reference.
In the prior art, one solution to reducing the incidence of artifacts in recompressed images originally compressed using the JPEG file format is described in the Chan article. As described therein, three test images are recompressed to various quality levels and the entry-wise quotients of the quantization matrices used during the recompression are analyzed. Chan provides heuristics to modify the transform coefficients of the image data after each requantization. Chan empirically observes favorable requantization conditions for each image, each of which appears to depend only upon the quantization matrices involved in an image-dependent manner. However, no explanation of this highly interesting phenomenon is given.
Therefore, there is a need for an approach to recompressing images compressed in the JPEG file format towards a selected target quality through the creation of a new quantization matrix that substantially minimizes the errors introduced through requantization and without requiring the iterative modification of image transform coefficients.